K-Way Merge? 先來點解釋吧!

K-Way Merge就是將k個已排序陣列，合併成一個單一的有排序陣列，這樣的技巧利用了已排序的輸入達到高效且有序的合併。

使用K-Way Merge的時間與空間複雜度
• 在時間複雜度上為O(N log k)，其中N為元素的總數
• 在空間複雜度上為O(k)，因為會在heap(堆)中儲存k個元素

K-Way Merge的使用時機?
• 當你需要合併多個有序陣列或有序list
• 須在多個已排序的陣列中，找出第k個最小或是最大的元素

上面這段描述看起來文謅謅的，我們來點輕鬆、愉快的圖解吧!
先從最簡單的範例來看-- Two-Way Merge
1.假設有兩個已排序陣列，這時兩個陣列都各有一個指針，指針皆指向陣列中index為0的整數，如下所示，指針以符號"^"標示:

arrA  =  [1, 5, 7]           arrB  =  [1, 3, 4]
          ^                            ^

2.這時我們使用另一個新的空陣列來存放合併後的新陣列

arrMerged = []

3.開始進行合併，arrA跟arrB兩個陣列中，指針指向的兩個元素進行比較，較小者可以放進arrMerged，若相同則隨機取其一放入。元素被放入arrMerged的陣列，指針則往右移動，如下:

arrA  =  [5, 7]           arrB  =  [1, 3, 4]
          ^                         ^
arrMerged = [1]

4.繼續進行指針位置的元素比較，一樣較小者則放入陣列arrMerged後，移動指針，如下:

arrA  =  [5, 7]           arrB  =  [3, 4]
          ^                         ^
arrMerged = [1, 1]

5.以此類推，直到兩個陣列裡面的元素都被放入arrMerged裡，便完成合併與排序

arrA  =  [5, 7]           arrB  =  [4]
          ^                         ^
arrMerged = [1, 1, 3]
-------------------------------------------
arrA  = [5, 7]           arrB  =  [ ]
         ^
arrMerged = [1, 1, 3, 4]
-------------------------------------------
arrA  =  [7]           arrB  =  [ ]
          ^
arrMerged = [1, 1, 3, 4, 5]
------------------------------------------
arrA  =  [ ]           arrB  =  [ ]

arrMerged = [1, 1, 3, 4, 5, 7]

看完上面的Two-Way Merge，我們再回到K-Way Merge吧!

K-Way Merge其實就是Two-Way Merge做法的2.0版，為什麼這樣說呢?

因為K-Way Merge就是先把多組陣列分為兩兩一組，每組當成一個單位來看，再用Two-Way Merge的技巧把每一組裡面的兩個陣列合併成一個，全部合併完成後，再重複剛剛的步驟，把合併完的陣列再兩兩一組，進行Two-Way Merge，不斷重複步驟，直到全部合併成一個陣列為止。

文字敘述可能讓人有些無法理解與想像，我找到一個動畫，完美詮釋了K-Way Merge的概念與技巧，也許可以幫助你理解
→ https://www.youtube.com/watch?v=vO961e332A4

Reference:
https://www.youtube.com/watch?v=vO961e332A4
https://medium.com/@vidyasagarr7/mastering-the-k-way-merge-algorithmic-pattern-for-technical-interviews-6db0e00a049f